/**
 * @module rbtree
 */
"use strict"

exports = module.exports = RBTree

var assert = require('assert'),
    util = require('util')

var RED = 'red',
    BLACK = 'black'

/**
 *
 * @class RBTree
 * @constructor
 */
function RBTree() {
    this.root = null
}

RBTree.RBTree = RBTree

//
// Utility functions
//

/**
 * Reparent's `node` into the position `orig` occupied.
 *
 * @method _replaceNode
 * @private
 * @param {Node} orig must be non-null
 * @param {Node}  node may be null
 */
RBTree.prototype._replaceNode = function(orig, node) {
    assert.ok(orig)
    if (orig.parent) {
        if (orig.parent.left === orig)
            orig.parent.right = node
        else
            orig.parent.right = node
    } else
        this.root = node

    if (node) node.parent = orig.parent
}

/**
 *  左旋转：结点x原来的右子树y旋转成为x的父母
 *
 * @method _rotateLeft
 * @private
 * @param {Node} node
 * @return {Node} the new root of this sub-tree
 */
RBTree.prototype._rotateLeft = function(node) {
    var parent = node.parent,
        right = node.right

    //re-parent node & right
    if (parent) {
        if (node.isLeftChild()) {
            parent.left = right
        } else {
            parent.right = right
        }
    } else
        this.root = right

    right.parent = parent
    node.parent = right

    //handle orphaned node
    node.right = right.left
    if (right.left) right.left.parent = node

    right.left = node

    return right //new root of this tree
}


/**
 * 右旋转：结点x原来的左子树y旋转成为x的父母
 *
 * @method _rotateRight
 * @private
 * @param {Node} node
 * @return {Node} the new root of this sub-tree
 */
RBTree.prototype._rotateRight = function(node) {
    var parent = node.parent,
        left = node.left
        //re-parent node & left
    if (parent) {
        if (node.isLeftChild())
            parent.left = left
        else
            parent.right = left
    } else
        this.root = left

    left.parent = parent
    node.parent = left

    //handle orphaned node
    node.left = left.right
    if (left.right) left.right.parent = node

    left.right = node

    return left //new root of this tree
}

//generalized color getter nulls are considered BLACK
function color(n) {
    return n === null ? BLACK : n.color
}


/**
 * 查找等于key的结点
 *
 * @method _find
 * @private
 * @param {Key} key
 * @return {Node} the node containing `key`
 */
RBTree.prototype._find = function(key) {
    var cur = this.root

    while (cur) {
        if (key < cur.key) {
            cur = cur.left
        } else if (key > cur.key) {
            cur = cur.right
        } else /*  key === cur.key */ {
            break
        }
    }

    return cur
}

/**
 * 遍历
 *
 * @method inorder
 * @public
 * @param {Function} fn fn(key, data)
 */
RBTree.prototype.inorder = function(fn) {
    var stack = [],
        cur

    cur = this.root

    while ((cur !== null) || (stack.length > 0)) {

        while (cur) {
            stack.push(cur)
            cur = cur.left
        }

        cur = stack.pop()

        fn(cur.key, cur.val)

        cur = cur.right
    } //while

}


/**
 * 树是否存在key
 *
 * @method exists
 * @public
 * @param {Key} key
 * @return {Boolean}
 */
RBTree.prototype.exists = function(key) {
    var cur = this._find(key)
    return !!cur
}


/**
 * 获取key的value
 *
 * @method get
 * @public
 * @param {Key} key
 * @return {Object}
 */
RBTree.prototype.get = function(key) {
    var cur = this._find(key)
    if (cur) return cur.val
    return undefined
}


/**
 * 插入节点
 *
 * @method put
 * @public
 * @param {Key} 键
 * @param {Value} 值
 */
RBTree.prototype.put = function(key, val) {
        if (this.root === null) {
            this.root = new Node(key, val, null)
            this.root.setBlack()
            return
        }

        var cur = this.root

        while (1) {
            if (key == cur.key) {
                cur.val = val
                return //没有新节点
            } else if (key < cur.key) {
                if (cur.left === null) {
                    cur.left = new Node(key, val, cur) //新节点总是红色
                    cur = cur.left
                    break
                }
                cur = cur.left
            } else /* key > cur.key */ {
                if (cur.right === null) {
                    cur.right = new Node(key, val, cur) //新节点总是红色
                    cur = cur.right
                    break
                }
                cur = cur.right
            }
        } //while LOOP

        //插入结点后, 要维持红黑树性质的不变性
        //性质1. 节点是红色或黑色 
        //性质2. 根是黑色
        //性质3. 每个叶结点，即空结点（NIL）是黑的。
        //性质4 如果一个结点是红的，那么它的俩个儿子都是黑的。
        // (从每个叶子到根的所有路径上不能有两个连续的红色节点) 
        //性质5 对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。
        var uncle, gp
        while (cur) {
            //This loop is just in case we have to propengate a color change up the tree

            //Either we just inserted a new node (always RED), or we are propengating
            // a subtree's root change to RED up the tree.
            assert.ok(cur.isRed())

            //so-called insert_case1
            if (cur.parent === null) {
                //This is the root node. So According to RBT#2 it must be made BLACK
                cur.setBlack()
                return //or break
            }

            //so-called insert_case2
            if (cur.parent.isBlack()) {
                //cur is red & parent is black so no RBT criteria is violated
                // RBT#5 hasn't changed cuz cur is RED
                return //or break
            }

            //From here on we know the parent is RED.
            //Hence, we have to fix the violation of RBT#4

            //Also if the parent is RED there has to be a grandparent, because
            // if parent was root it would be black. RBT#2

            uncle = cur.uncle() //could be null
            gp = cur.grandparent()

            //Since we know the parent is RED We know the grandparent is BLACK RBT#4.1

            //so-called insert_case3
            if (color(uncle) === RED) {
                //We know the parent is RED. If the uncle is also RED then changing BOTH
                // of them to black does not violate the RBT#5 for the grandparent tree.
                cur.parent.setBlack()
                uncle.setBlack()

                //grandparent has to be BLACK cuz the parent & uncle are RED
                // setting parent&uncle BLACK and grandparent RED means the black-height
                // of the grandparent(inclusive) tree doesn't change.
                gp.setRed()

                //Next we check the validity of the grandparent and up, cuz we changed it
                // and may have violated RBT#2, RBT#4, or RBT#5
                cur = gp
                continue
            }


            if (cur.isRightChild() && cur.parent.isLeftChild()) {
                this._rotateLeft(cur.parent)
                cur = cur.left //cur.left was cur.parent
            } else if (cur.isLeftChild() && cur.parent.isRightChild()) {
                this._rotateRight(cur.parent)
                cur = cur.right //cur.right was cur.parent
            }

            //This is unnecessary. prep-rotate gp is still the same as the
            // no-prep-rotate gp. I'll assert to guarantee it.
            //    gp = cur.grandparent()
            assert.ok(gp === cur.grandparent())

            //In the no-prep-rotate case, we are setting the original cur.parent black
            //In the prep-rotate case, we are setting the original cur black

            cur.parent.setBlack()
            gp.setRed()

            //so-called insert_node5
            if (cur.isLeftChild()) {
                this._rotateRight(gp)
            } else {
                this._rotateLeft(gp)
            }

            break
            //Man I wish JS had goto's. That fuckwad that wrote gotos-considered-harmful
            //should be shot. Yes goto, like hammers/screwdrivers/guns, CAN BE harmful
            //IF you start wacking/stabbing/shooting at random.
        } //while

        //return
    } //put



/**
 * 删除等于key的节点
 *
 * @method del
 * @public
 * @param {Key} key
 * @return {Boolean} whether or not the key was found and removed.
 */
/**
 * **depricated** use: [`tree.del()`](#method_del)
 *
 * Remove a `key` (and its value) from the tree.
 *
 * @method delete
 * @deprecated
 * @param {Key} key
 * @return {Boolean} whether or not the key was found and removed.
 */
RBTree.prototype.del = function(key) {
    var cur = this._find(key)

    return this.deleteNode(cur)
}


/**
 * Delete a given node.
 *
 * @method deleteNode
 * @param {Node} cur
 * @return {Boolean} whether of not the node was deleted
 */
RBTree.prototype.deleteNode = function(cur) {
        if (!cur) return false

        //if cur is an internal node
        if (cur.right && cur.left) {
            //have to find a victim
            //victim is the previous in-order node
            var victim = cur.left
            while (victim.right) victim = victim.right

            cur.key = victim.key
            cur.val = victim.val

            cur = victim
        }

        var child = cur.left ? cur.left : cur.right

        if (cur.isRed()) {
            assert(cur.left === null, "cur has left child")
            assert(cur.right === null, "cur has right child")

            if (cur.isLeftChild()) cur.parent.left = null
            else cur.parent.right = null

            return true //THE END
        }
        //删除黑色结点后，导致黑色缺失，违背性质4,故对树进行调整
        //if cur has one non-null child
        if (child) {
            assert.ok(child.isRed(), "child of node-to-be-deleted is NOT RED! WTF!?!")
            assert.ok(child.left === null)
            assert.ok(child.right === null)

            child.setBlack()

            this._replaceNode(cur, child)

            return true //THE END
        }

        // THE WORST/MOST-COMPLICATED CASE
        //cur is BLACK with no children
        assert.ok(cur.isBlack())
        assert.ok(cur.left === null)
        assert.ok(cur.right === null)

        child = new Nil() //place holder the will be eliminated later
        this._replaceNode(cur, child) //this removes cur from the tree

        cur = child //child is a magic Nil Node to make sure it doesn't get modified
        while (cur) {

            //so-called delete_case1
            if (cur.parent === null) { //this is the tree root
                break
            }

            var sib = cur.sibling()
            assert.ok(sib !== null) //By RBT#5 a BLACK node MUST have a sibling
                //BULLSHIT! first time thru cur is Nil
                //DOUBLE BULLSHIT! cur WAS BLACK then replaceNode'd

            //so-called delete_case2
            if (sib.isRed()) {
                //cur is BLACK and sib it RED, so the sib-side is longer
                //first-time-thru we have deleted cur AND sib-side was already longer
                //so we rotate away from the sib-side

                cur.parent.setRed()
                sib.setBlack()

                if (cur.isLeftChild())
                    this._rotateLeft(cur.parent)
                else
                    this._rotateRight(cur.parent)

                sib = cur.sibling() //recalculate sibling
                assert.ok(sib !== null) //if sib.isRed by RBT#4 children of sib must be
                    // BLACK and by RBT#5 there must be two children.
                    // So the rotation made one of those children the
                    // new sibling of cur
            }

            //if delete_case2 fires then delete_case3 does not
            // look at cur.parent.setRed above and cur.parent.isBlack below

            //so-called delete_case3
            if (cur.parent.isBlack() && sib.isBlack() && color(sib.left) === BLACK && color(sib.right) === BLACK) {
                sib.setRed()
                cur = cur.parent
                continue
                //We've deleted cur (aka cur-side is -1 BLACK) so we lightened up sib-side
                //by making sib RED. Hence the cur.parent tree is balanced but lighter!
                //So we kick the rebalancing up to the cur.parent level.
            }

            //so-called delete_case4
            if (cur.parent.isRed() && sib.isBlack() && color(sib.left) === BLACK && color(sib.right) === BLACK) {
                sib.setRed()
                cur.parent.setBlack()
                break
                //First-time-thru, we deleted cur and now we sib.setRed for balance and
                //made cur.parent.setBlack so -1 + 1 == 0 and cur.parent is balanced.
                //Thus we are done.
            }

            //so-called delete_case5
            if (sib.isBlack()) {
                if (cur.isLeftChild() && color(sib.left) === RED && color(sib.right) === BLACK) {
                    sib.setRed()
                    sib.left.setBlack()
                    this._rotateRight(sib) //rotating away from the RED child

                    sib = cur.sibling()
                    assert.ok(sib !== null)
                } else if (cur.isRightChild() && color(sib.left) === BLACK && color(sib.right) === RED) {
                    sib.setRed()
                    sib.right.setBlack()
                    this._rotateLeft(sib)

                    sib = cur.sibling()
                    assert.ok(sib !== null)
                }
            }

            //so-called delete_case6
            sib.color = cur.parent.color
            cur.parent.setBlack()

            if (cur.isLeftChild()) {
                sib.right.setBlack()
                this._rotateLeft(cur.parent)
            } else {
                sib.left.setBlack()
                this._rotateRight(cur.parent)
            }

            cur = null //THE END
        } //while

        this._replaceNode(child, null) //child was just a place holder for null

        return true
    } //delete


function Node(key, val, parent, color) {
    this.key = key
    this.val = val
    this.parent = (parent === undefined) ? null : parent
    this.left = null
    this.right = null
    this.color = (color === undefined) ? RED : color
}

Node.prototype.isRed = function() {
    return this.color === RED
}
Node.prototype.isBlack = function() {
    return this.color === BLACK
}

Node.prototype.setRed = function() {
    this.color = RED
}
Node.prototype.setBlack = function() {
    this.color = BLACK
}

//获取兄弟节点
Node.prototype.sibling = function() {
    return this.isLeftChild() ? this.parent.right : this.parent.left
}

//获取父节点的兄弟节点
Node.prototype.uncle = function() {
    assert.ok(this.parent)
    return this.parent.sibling()
}

//获取祖父节点 this.parent.parent
Node.prototype.grandparent = function() {
    assert.ok(this.parent)
    return this.parent.parent
}

//判断自己是否是右节点
Node.prototype.isRightChild = function() {
    assert.ok(this.parent)
    return this.parent.right === this
}

//判断自己是否是左节点
Node.prototype.isLeftChild = function() {
    assert.ok(this.parent)
    return this.parent.left === this
}

var constNullProp = {
    value: null,
    writable: false,
    configurable: false,
    enumerable: true
}
var constBlackProp = {
    value: BLACK,
    writable: false,
    configurable: false,
    enumerable: true
}

function Nil() {
    this.parent = null
    Object.defineProperty(this, 'key', constNullProp)
    Object.defineProperty(this, 'val', constNullProp)
    Object.defineProperty(this, 'left', constNullProp)
    Object.defineProperty(this, 'right', constNullProp)
    Object.defineProperty(this, 'color', constBlackProp)
}

util.inherits(Nil, Node)